#include "main.h"
// 0 - элемента в массиве нет
int LinearSearch(int *a, int beg, int end, int key)
{
	for(int i = beg; i <= end; i++)
	{
		if (a[i] == key) return ((i+ 1 - beg)*2);
	}
	return 0;
}
int QuickLinearSearch(int *a, int beg, int end, int key)
{
	for(int i = beg; i <= end; i++)
	{
		if (a[i] == key) return ((i - beg +1));
	}
	return 0;
}
int QuickLinearSearchInSortedArray(int *a, int beg, int end, int key)
{
	for(int i = beg; i <= end; i++)
	{
		if (a[i] == key) return ((i + 1 - beg));
		if (a[i] > key) return 0;
	}
	return 0;
}
int BinarySearch(int *a, int beg, int end, int key)
{
	if (!(beg <= end))
	{
		return 0;
	};
	int middle = (beg + end)/2;
	if (key == a[middle]) return 1;
	else
	{
		if (key > a[middle])
		{
			int temp = BinarySearch(a, middle + 1, end, key);
			return (temp?2 + temp:temp);
		};
		int temp = BinarySearch(a, beg, middle - 1, key);
		return (temp?2 + temp:temp);
	}
	return 0;
}
int BlockSearch(int *a, int size, int key)
{
	int X = 0;
	while (X*X <= size) X++;
	X--;
	for (int i = X - 1; i < size; i += X) if (key <= a[i])
	{
		if (key == a[i]) return ((i+1)/X);
		int temp = BinarySearch(a, i - X + 1, i, key);
		return (temp?((i+1)/X) + temp:temp);
	}
};
